import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-10-29
 * Time:9:58
 */
class IntInt implements Comparator<Integer>{

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}
public class Test {
    //利用堆进行排序
    //从小到大排序的话。用大根堆，小根堆排序，只能找到最小的值，但是不能保证里面的树是排好序的



    //求第k个最小的值
    //先建立一个k个值的大根堆
    //然后第一个就是第k个小的值
    public int smallestK1(int[] arr, int k) {
        if(arr.length==0||k<0){
            return 0;
        }
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new IntInt());
        for (int i = 0; i < arr.length; i++) {
            if(i<k){
                priorityQueue.offer(arr[i]);
            }else{
                //判断是不是比堆顶元素大
                if(arr[i]>priorityQueue.peek()){
                    priorityQueue.poll();
                    priorityQueue.offer(arr[i]);
                }
            }
        }
        int tmp=priorityQueue.peek();
        return tmp;
    }
    //最小的k个数
    //利用小根堆
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.offer(arr[i]);
        }
        int[] array=new int[k];
        for (int i = 0; i < k; i++) {
            array[i]=priorityQueue.poll();
        }
        return array;
    }
    //利用大根堆
    //不用整体建堆

    public int[] smallest(int[] arr, int k) {
        if(arr.length==0||k<0){
            return new int[0];
        }
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new IntInt());
        for (int i = 0; i < arr.length; i++) {
            if(i<k){
                priorityQueue.offer(arr[i]);
            }else{
                //判断是不是比堆顶元素大
                if(arr[i]>priorityQueue.peek()){
                    priorityQueue.poll();
                    priorityQueue.offer(arr[i]);
                }
            }
        }
        int [] tmp=new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i]=priorityQueue.poll();
        }
        return tmp;
    }
}
